/**
 * 文斌大大龙算法 【57】篇
 * LeetCode 算法第 239 题
 * 滑动窗口最大值
 * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
 * 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
 * 返回滑动窗口的最大值;
 *
 * 算法思路 双端队列
 */
const maxSlidingWindow = function(nums, k){
    // windowIdxArr 表示窗口中的下标位置，res 存最终结果
    let [windowIdxArr, res] = [[],[]];
    for (let i = 0; i < nums.length; i++) {
        // 当小标的间距超出了 K 就把窗口最左边的元素出队
        if(i >= k && windowIdxArr[0] < i - k){
            windowIdxArr.shift();
        }
        // 重点是这里，向前依次比较队尾的元素，让队列坐标对应元素单调
        while(windowIdxArr.length && nums[windowIdxArr.slice(-1)] <= nums[i]){
            windowIdxArr.pop();
        }
        //清除完不符合大小条件的元素后，新加入元素进入窗口
        windowIdxArr.push(i);
        // 把本轮窗口中最大的进入结果数组
        // 注意至少有 3 个元素， 下标从 0 开始
        if(i >= k - 1){
            // 因为队列是单调的，本轮最大就是 idx 的第一个对应元素
            res.push(nums[windowIdxArr[0]]);
        }
    }
    return res;
}

/**
 * 文斌大大龙算法第 【58】 篇
 *
 * 二叉搜索树最近公共祖先
 *
 * 二叉树公共最先使用层序遍历可有记录父子关系
 *
 * 热茶搜索树可以使用期特性，简化搜索方式
 */
const lowestCommonAncestor = function(root,p,q){
    while(root){
        if(root.value > p.value && root.value > q.value){
            root = root.left;
        }else if(root.value < p.value && root.value < q.value){
            root = root.right;
        }else{
            return root;
        }
    }
};

/**
 * 文斌大大龙算法第【59】篇
 * LeetCode 第 【169】题
 * 多数元素
 * 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
 *
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素
 *
 * 要求 时间复杂度是 O(n) 空间复杂度是 O(1);
 *
 * 解题思路 消除法 相同的相加，不同的相互抵消
 *
 */
const majorityElement = function(nums){
    let [majority, listLength] = [null, 0];
    for (let num of nums) {
        // list空了，说明全被抵消了
        if(listLength === 0){
            majority = num;
        }
        // 跟老大相同时就加入，不同就抵消
        if(num === majority){
            listLength++;
        }else{
            listLength--;
        }
    }
    return majority;
}

/**
 * 文斌大大龙算法【60】篇
 * LeetCode第 148 题目
 * 排序链表
 * 解法思路 链表合并 归并排序
 */

const mergeTwoList = function(l1,l2){
    if(l1 === null){
        return l2;
    }else if(l2 === null){
        return l1;
    }else if(l1.value < l2.value){
        l1.next = mergeTwoList(l1.next, l2);
        return l1;
    }else{
        l2.next = mergeTwoList(l2.next,l1);
        return l2;
    }
};

const sortList = function(head){
    // 判断是否为空
    if(!head || !head.next){
        return head;
    }
    // 快慢指针来分割链表
    let [fast, slow, preSlow] = [head,head,null];
    while(fast && fast.next){
        // 记录下可能断开的点，就是当前slow的位置
        preSlow = slow;
        // 快指针
        fast = fast.next.next;
        slow = slow.next;
    }
    // 要把第一个链表尾部置空断开
    preSlow.next = null;
    let l = sortList(head);
    let r = sortList(slow);
    return mergeTwoList(l,r);
}
/**
 * 文斌打大龙算法 【63】篇
 *
 * LeetCode 37 题 解数独
 *
 */

const solveSudou = function(board){
    // 枚举值
    const enumVal = ['1', '2', '3', '4', '5', '6', '7', '8', '9'];

    const rows = new Array(9).fill(0).map(it => new Set(enumVal));
    const cols = new Array(9).fill(0).map(it => new Set(enumVal));
    const blocks = new Array(9).fill(0).map(it => new Set(enumVal));

    // 根据坐标，获取所在的子盒子的索引
    const getBoxIndex = (i,j) => {
        return Math.floor(i / 3) * 3 + Math.floor(j / 3);
    };

    // 根据现有的已填的数字，精简可选数据集，把不能填写的数字从可选数据集中删除
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            if(board[i][j] !== "."){
                // 当前行出现这个数字，这个数字就不能在这一行出现，就应该从这一行的“可选”数据集中删除
                // 可选的意思就是选了之后仍然合法
                rows[i].delete(board[i][j]);
                cols[j].delete(board[i][j]);
                blocks[getBoxIndex(i,j)].delete(board[i][j]);
            }
        }
    }

    const dfs = (i,j) => {
        // 列超过最边界坐标
        if(j > 8){
            // 行 +1;
            i++;
            // 列回到起点
            j = 0;
            if(i > 8){
                return true;
            }
        }
        // 如果不是空白格，递归填下一个格
        if(board[i][j] !== "."){
            return dfs(i, j+1);
        }

        const boxIndex = getBoxIndex(i,j);
        // 枚举出所有的选择 1-9
        for (let num = 1; num <= 9; num++){
            const cur = String(num);
            // 当前选择必须在三个set中都存在，如果有一个不存在，就说明发生了冲突，跳过该选择
            if(!rows[i].has(cur) || !cols[j].has(cur) || !blocks[boxIndex].has(cur)){
                continue;
            }
            // 做出选择，填上该数据
            board[i][j] = cur;
            // 删掉这个可填选项
            rows[i].delete(cur);
            cols[j].delete(cur);
            blocks[boxIndex].delete(cur);
            // 如果基于当前选择，填下一个数组可以解出数独，返回true
            if(dfs(i, j+1)) return true;
            // 回溯，恢复为空白格
            board[i][j] = ".";
            // 将之前删掉的当前数字，加回来
            rows[i].add(cur);
            cols[j].add(cur);
            blocks[boxIndex].add(cur);
        }
        // 尝试了1-9, 每个都往下递归，都不能完成，返回false
        return false;
    };
}

/**
 * 文斌打大龙算法【65】篇
 * LeetCode 第 300 题目
 * 最长递增子序列
 *
 * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 * 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
 * 例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
 *
 * 解题思路 动态规划题目
 *
 * 我们还是按照基本步骤来
 *  寻找最优子结构(状态表示)
 *  归纳状态转移方程(状态计算)
 *  边界初始化
 *
 *  dp数组记录的是长度
 *  dp[i] = Math.max(dp[i], dp[j] + 1)
 */
const lengthOfLIS = function(nums){
    if(!nums || !nums.length){
        return 0;
    }
    // dp数组 边界初始化
    let dp = new Array(nums.length).fill(1);
    let max = 1;
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if(nums[i] > nums[j]){
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        max = Math.max(dp[i],max);
    }
    return max;
};

/**
 * 文斌打大龙算法【67】篇
 * leetcode算法第215题
 * 数组中第K个大的元素
 * 使用快排的方法
 */

const findKthLargest = function(nums,k){
    const n = nums.length;
    const quickSort = (left, right) => {
        if(left < right){
            let pivot = nums[right];
            let pivotIndex = left;
            for (let i = left; i < right; i++) {
                if(nums[i] < pivot){
                    [nums[i], nums[pivotIndex]] = [nums[pivotIndex],nums[i]];
                    pivotIndex++;
                }
            }
            [nums[right], nums[pivotIndex]] = [nums[pivotIndex], nums[right]];
            // 当 n - k === pivotIndex 时
            // 左边元素比 nums[n-k] 小， 右边比 nums[n-k]大，nums[n-k]就是第K大的元素
            if(n - k < pivotIndex){
                // n - k 小于 pivotIndex, 则在左边继续寻找
                quickSort(left,pivotIndex - 1);
            }else{
                // n - k 大于 pivotIndex,则在 ‘右边继续寻找’
                quickSort(pivotIndex + 1, right);
            }
        }
    };
    quickSort(0,n-1);
    return nums[n - k];
};

/**
 * 文斌大大龙算法 【132】 篇
 * LeetCode 第 202 题
 * 编写一个算法来判断一个数 n 是不是快乐数。
 * 解题思路 快慢指针，判断链表是否有环
 */

const isHappy = function(n){
    // 这是计算一个数的各位数平方和函数
    const calcSum = (num) => {
        let numArr = num.split("");
        numArr.reduce((acc, item) => acc + parseInt(item) * parseInt(item), 0);
    }
    // 定义快慢指针，一个走一步，一个走两步
    let [slow, fast] = [n,n];
    do{
        slow = calcSum(slow);
        fast = calcSum(calcSum(fast));
    }while (fast != slow);

    return fast == 1;
};

// leetcode 437 copy books的问题  困难 目前国内leetcode没有这个题目
// 解法一： 动态规划求解
const copyBook = function(books, K){
    let n = books.length;
    if(n === 0){
        return 0;
    }
    const dp = new Array(k+1).fill(new Array(n+1).fill(0));
    dp[0][0] = 0;
    let i=0,j=0,k=0;
    for(i=1;i<=n;i++){
        dp[0][i] = Number.MAX_SAFE_INTEGER;
    }
    for(k=1;k<=K;++k){
        dp[k][0] = 0;
        for(i=1;i<=n;++i){
            dp[k][i] = Number.MAX_SAFE_INTEGER;
            let sum = 0;
            for(j=i;j>=0;--j){
                dp[k][i] = Math.min(dp[k][i],Math.max(dp[k-1][j],sum));
                if(j > 0){
                    sum += books[j-1];
                }
            }
        }
    }
    return dp[k][n];
}

/**
 * 解法二  动态规划求解
 * @param books
 * @param limit
 * @param k
 * @returns {boolean}
 */
const checkValid = function(books, limit, k){
    let count = 1;
    let sum = 0;
    let len = books.size();
    for(let i = 0; i < len; i++){
        if(books[i] > limit) return false;
        if(books[i] + sum > limit){
            count++;
            sum = books[i];
        }else{
            sum += books[i];
        }
    }
    return count <= k;
}

const copyBooks2 = function(books,k){
    let len = books.length;
    let maxPage = 0, sum = 0;
    for(let i=0; i<len;i++){
        maxPage = Math.max(maxPage,books[i]);
        sum += books[i];
    }
    let left = maxPage, right = sum;
    while(left + 1 < right){
        let mid = left + Math.floor((right - left) / 2);
        if(checkValid(books,mid, k)){
            right = mid;
        }else{
            left = mid;
        }
    }
    if(checkValid(books,left,k)) return left;
    return right;
}

/**
 * 给定一个数组和一个数字，请在这个数组的元素之间添加+-符号，使这个数组元素运算之后的结果是这个数字，
 * 比如{2,3,4}1 则2+3-4=1输出这样的等式
 */

const solution = function(nums,target){
    let result = [];
    let rest = nums[0];
    let len = nums.length;
    const dfs = (path,startIndex, rest) => {
        if(startIndex === len && rest === target){
            result.push(path.slice().join(""));
            return ;
        }else if(startIndex >= len){
            return;
        }

        path.push('+');
        path.push(nums[startIndex]);
        dfs(path,startIndex + 1, rest + nums[startIndex]);
        path[path.length - 2] = '-';
        dfs(path,startIndex + 1, rest - nums[startIndex]);
    }
    dfs([nums[0]],1, rest);
    return result;
}


/**
 * 微软历年面试题目
 * leetcode 215   第 K 个最大元素      【快拍】
 * Leetcode 124   二叉树中的最大路径    【递归】
 * leetcode 236   二叉树的最近公共祖先   【递归，分治】
 * leetcode 206   链表反转
 * leetcode 3     解码方法
 * leetcode 94    二叉树中序遍历
 * leetcode 15    三个数之和
 * leetcode 121   买卖股票最佳时机
 * leetcode 48    旋转图像
 * leetcode 543   二叉树直径
 * leetcode 53    最大子序列和
 * leetcode 4     两个有序数组寻找中位数
 * leetcode 110   平衡二叉树 自底向上球阀
 * leetcode 146   LRU  双向队列 + Hash表
 * leetcode 103   二叉树的锯齿形遍历
 * leetcode 415   字符串相加
 * leetcode 62    不同路径
 * leetcode 22    括号生成
 * leetcode 98    验证二叉树
 * 剑指offer 46    数组翻译字符串
 * leetcode 84    图形中最大的矩形
 * leetcode 120   三角形最小路径和
 * LeetCode 5     最长回文子串
 * leetcode 867   转置矩阵
 * leetcode 560   和为 K 的子数组
 * leetcode 986   区间列表的交集
 * leetcode 78    子集
 * leetcode 907   子数组的最小值之和
 * leetcode 163   寻找峰值
 * leetcode 547   朋友圈  省份数量的题目
 * leetcode 1013  将数组分成和相等的三个部分
 * leetcode 34    在排序数组中查找元素的第一个位置和最后一个位置
 * leetcode 142   环形链表
 * leetcode 572   另一个树的子树
 * leetcode 154   寻找旋转排序数组中的最小值II
 * leetcode 704   二分查找
 * leetcode 151   反转字符串里的单词
 * leetcode 171   Excel表列序号
 * leetcode 39    组合总和
 * leetcode 150   逆波兰表达式求值
 * leetcode 283   移动 0  快排的思想
 */


